using System;
using System.Threading;
using System.Diagnostics;

namespace Dida
{
	/// <summary>
	/// An thread-safe non blocking queue, implemented using interlocked operations.
	/// </summary>
	/// <typeparam name="T">The type of the items in the queue.</typeparam>
	public class InterlockedQueue<T>
		where T : class
	{
		class Node
		{
			public T value;
			public Node next;
		}

		Node dum = new Node();

		Node head = null;
		Node tail = null;

		public InterlockedQueue()
		{
			dum.next = dum;
			head = tail = dum;
		}

		public void Push(T value)
		{
			Node node = new Node();
			node.value = value;
			node.next = dum;

			while(true)
			{
				Node curHead;
				while(true)
				{
					curHead = head;

					Node curTailNext = tail.next;
					if (tail.next == dum)
					{
						head = curHead = dum;
						break;
					}

					if(curHead.next == dum)
						break;

					Thread.MemoryBarrier();
					Interlocked.CompareExchange(ref head,curHead.next,curHead);
				}

				Thread.MemoryBarrier();
				Node oldNext = Interlocked.CompareExchange(ref head.next, node, dum);
				if (oldNext == dum)
					break;
			}
		}

		public T Pop()
		{
			Node ret;

			do
			{
				ret = tail.next;
				if (ret == dum)
					return null;
			}
			while(Interlocked.CompareExchange(ref tail.next,ret.next,ret) != ret);

			return ret.value;
		}

		public T Peek()
		{
			Node curTail = tail.next;
			if (curTail != dum)
				return curTail.value;
			else
				return null;
		}
	}
}